# 二分查找 旋转数组


class Solution:
    # 二分后，一定有一部是有序的
    def search(self, nums, target):
        if not nums:
            return -1
        l, r = 0, len(nums) - 1

        while l <= r :
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            # 先判断哪一部分是有序，在有序中执行操作
            # 这部分是有序的
            if nums[0] <= nums[mid]:
                # 在有序部分
                if nums[0] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums) - 1]:
                    l = mid + 1
                else:
                    r = mid - 1
            


        return -1




if __name__ == "__main__":

    a = [4,5,6,7,0,1,2]

    sol = Solution()
    res = sol.search(a, 0)
    print(res)
    



